反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

方法一:迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while(cur != null) {
      ListNode next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    return prev;
  }
}

var reverseList = function(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
• 空间复杂度：O(1)

执行结果：通过

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

• 内存消耗：38.1 MB, 在所有 Java 提交中击败了70.48%的用户

方法二：递归

class Solution {
  public ListNode reverseList(ListNode head) {
    //递归终止条件是当前为空，或者下一个节点为空
    if(head == null || head.next == null) {
      return head;
    }
    //这里的cur就是最后一个节点
    ListNode newHead = reverseList(head.next);
    //这里请配合动画演示理解
    //如果链表是 1->2->3->4->5，那么此时的cur就是5
    //而head是4，head的下一个是5，下下一个是空
    //所以head.next.next 就是5->4
    head.next.next = head;
    //防止链表循环，需要将head.next设置为空
    head.next = null;
    //每层递归函数都返回cur，也就是最后一个节点
    return newHead;
  }
}

var reverseList = function(head) {
  if (head == null || head.next == null) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

执行结果：通过

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

• 内存消耗：38.5 MB, 在所有 Java 提交中击败了8.90%的用户